﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm
{
    class Right
    {
        private bool[] searchList;
        private Dictionary<int, Order> rightList;
        private List<int> cuttingList;
        public Right()
        {
            int testCase = GetConsole.GetInt();
            for (int T = 1; T <= testCase; T++)
            {
                int rightCount = GetConsole.GetInt(); //조명의 수
                int orderCount = GetConsole.GetInt(); //입력 라인 수
                rightList = new Dictionary<int, Order>();

                for (int i = 1; i <= rightCount; i++)
                {
                    rightList.Add(i, new Order());
                }
                for (int i = 1; i <= orderCount; i++)
                {
                    int first = GetConsole.GetInt();
                    int last = GetConsole.GetInt();
                    rightList[first].AddNext(last);
                    rightList[last].AddBefore(first);
                }
                //루프 찾기
                int loopCount = 1;
                while (loopCount > 0)
                {
                    cuttingList = new List<int>();
                    searchList = new bool[rightCount + 1];
                    for (int i = 1; i <= rightCount; i++)
                    {
                        if (!searchList[i]) //이미 검색한 노드가 아니면
                        {
                            foreach (int index in rightList[i].next)
                            {
                                List<int> loopList = new List<int>();
                                loopList.Add(i);
                                FindLoop(index, loopList, i);
                            }
                        }
                    }
                    //루프 제거
                    for (int i = 0; i < cuttingList.Count; i += 2)
                    {
                        rightList[cuttingList[i]].DelNext(cuttingList[i + 1]);
                        rightList[cuttingList[i + 1]].DelBefore(cuttingList[i]);
                    }
                    loopCount = cuttingList.Count;
                }
                int count = 0;
                foreach (Order order in rightList.Values)
                {
                    if (order.before.Count == 0)
                    { count++; }
                }
                Console.WriteLine("Case " + T + ": " + count);
                Console.ReadLine(); //테스트 케이스 사이 공백 처리
            }
        }

        private void FindLoop(int nowIndex, List<int> loopList, int beforeIndex)
        {
            if (searchList[nowIndex]) //이미 검색한 노드이면
            {
                return;
            }
            searchList[nowIndex] = true;
            if (loopList.Contains(nowIndex))//루프일 경우
            {
                //현재 노드가 루프이면 유입경로가 2 이상인 노드의 루프 제거
                if (rightList[loopList[0]].before.Count > 1)
                {
                    cuttingList.Add(loopList[loopList.Count - 1]);
                    cuttingList.Add(loopList[0]);
                    return;
                }
                else
                {
                    for (int i = 1; i < loopList.Count; i++)
                    {
                        if (rightList[loopList[i]].before.Count > 1)
                        {
                            cuttingList.Add(loopList[i - 1]);
                            cuttingList.Add(loopList[i]);
                            return;
                        }
                    }
                }
                //그런 노드가 없을 경우 아무 링크나 제거
                cuttingList.Add(loopList[0]);
                cuttingList.Add(loopList[1]);
                return;
            }
            else
            {
                loopList.Add(nowIndex);
                foreach (int index in rightList[nowIndex].next)
                {
                    FindLoop(index, loopList, nowIndex);
                }
            }
        }
    }
    class Order
    {
        public List<int> before;
        public List<int> next;
        public Order()
        {
            before = new List<int>();
            next = new List<int>();
        }
        public void AddNext(int index)
        {
            if (!next.Contains(index))
            {
                next.Add(index);
            }
        }
        public void AddBefore(int index)
        {
            if (!before.Contains(index))
            {
                before.Add(index);
            }
        }
        public void DelNext(int index)
        {
            next.Remove(index);
        }
        public void DelBefore(int index)
        {
            before.Remove(index);
        }
    }
}
